Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.
On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares / Bonacina, I.; Galesi, N.; Lauria, M.. - 241:(2022), pp. 1-15. (Intervento presentato al convegno 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022 tenutosi a Vienna, Austria1) [10.4230/LIPIcs.MFCS.2022.23].
On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares
Bonacina I.
;Galesi N.
;Lauria M.
2022
Abstract
Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.File allegati a questo prodotto
| File | Dimensione | Formato | |
|---|---|---|---|
|
Bonacina_On-Vanishing _2022.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
760.32 kB
Formato
Adobe PDF
|
760.32 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
